package tree;

import java.util.*;

/**
 * 94. 二叉树的中序遍历
 * 简单
 * 相关标签
 * 相关企业
 * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [1,null,2,3]
 * 输出：[1,3,2]
 * 示例 2：
 * <p>
 * 输入：root = []
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：root = [1]
 * 输出：[1]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 树中节点数目在范围 [0, 100] 内
 * -100 <= Node.val <= 100
 * <p>
 * <p>
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 */
public class InorderTraversal_94 {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    public static void main(String[] args) {
        TreeNode_94 treeNode94 = new TreeNode_94(3, null, null);
        TreeNode_94 rootRight = new TreeNode_94(2, treeNode94,null);
        TreeNode_94 root = new TreeNode_94(1,null,rootRight);
        System.err.println(inorderTraversal(root));
    }

    public static List<Integer> inorderTraversal(TreeNode_94 root) {
        //返回的结果集
        List<Integer> res = new ArrayList<>();
        //创建一个栈
        Deque<TreeNode_94> stack = new LinkedList<>();
        //如果当前节点不为空或者当前栈不为空，就继续循环
        while(root != null || !stack.isEmpty()){
            //如果当前节点不为空，就继续循环
            //这个循环的目的是找到当前结点最左边的子结点
            while(root != null){
                //将当前结点压入栈
                stack.push(root);
                //调整root指向，指向左节点
                root = root.left;
            }
            //从栈中取出结点
            root = stack.pop();
            //将该值添加进结果集
            res.add(root.val);
            //调整root指向，指向右节点
            root = root.right;
        }
        return res;
    }
}
